import java.util.ArrayList;
import java.util.List;

/**
 * 回溯算法-组合总数|||-力扣216
 */
public class Practice_16 {
    public static List<List<Integer>> result = new ArrayList<>();
    public static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        int n = 7;
        int k = 3;
        combine(9, 3);

        System.out.println(result);
    }
    public static List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }

    public static void backtracking(int n, int k, int startindex) {

        if (path.size() == k) {
            int sum = 0;
            for (int m = 0; m < path.size(); m++) {
                sum = sum + path.get(m);
            }
            if (sum == n) {
                List<Integer> tmp = new ArrayList<>(path);//每次path符合要求后，把path的值放到临时变量tmp里，再放到result里。此时保持path容器唯一，去做装值、递归的操作。不能直接用result.add(path)
                result.add(tmp);//达到预定的数量，必须收集结果；
                return;//达到预定的数量必须return ；
            } else {
                //此处不符合收集结果的条件，可以不收集结果；
                return;//达到预定的数量必须return ；
            }

        }
        for (int i = startindex; i <= 9 - (k - path.size()) + 1; i++) {//i <=9-(k-path.size())+1 为减支，如果不减支则写成i<=9
            path.add(i);
            backtracking(n, k, i + 1);
            path.remove(path.size() - 1);//去除最后一个值（回溯思想）
        }
    }
}
